package com.practice.zuocy.trainingcamp001.class04;

/**
 * KMP算法
 */
public class Code01_KMP {
	// KMP主流程
    // O(N)
	public static int getIndexOf(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			// 过滤无效参数
			return -1;
		}
		char[] str = s.toCharArray();
		char[] match = m.toCharArray();
		int x = 0; // str中当前比对到的位置
		int y = 0; // match中当前比对到的位置

        // 得到next数组
		// M  M <= N   O(M)
		int[] next = getNextArray(match); // next[i]  match中i之前的字符串match[0...i-1]最长的前后缀相等的长度

		// O(N)
		while (x < str.length && y < match.length) {
			if (str[x] == match[y]) {
			    // 比对到的位置是相等的字符，x和y共同往右移动
				x++;
				y++;
			} else if (next[y] == -1) { // y == 0 可以改成 if(y==0)
			    // 比对到的位置是不相等的字符，并且next[y] == -1，
                // 说明y已经往左跳到了0位置（match的0位置），让x++后重新与y位置（match的0位置）匹配
				x++;
			} else {
				// 不匹配但是y还能往回跳，那就让y往左跳(y = next[y])，x不动
				y = next[y];
			}
		}
		// 最后有如下几种情况：
        // (1)x越界了y没有越界，说明匹配不到，返回-1
        // (2)x没越界，y越界了，说明能匹配上，返回匹配出的开头
        // (3)x越界了，y越界了，说明能匹配上。
        // 将3种情况整合一下
		return y == match.length ? x - y : -1;
	}

	// next数组（y下一次跳到哪儿）
	// M   O(M)
	public static int[] getNextArray(char[] match) {
		if (match.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[match.length];
		next[0] = -1;
		next[1] = 0;
		int i = 2;
		// cn代表，cn位置的字符，是当前和i-1位置比较的字符
		int cn = 0;// i从2开始计算，i-1位置的字符的next[i-1]==nest[1]==0，所有cn初始为0，很合理！  同时next[i-1]==cn
		while (i < next.length) {
			if (match[i - 1] == match[cn]) { // 跳出来的时候
				// 这一句的意思：
				// (1) next[i] = cn+1;
				// (2) i++;
				// (3) 此时的next[i-1]=cn+1，说明要用cn+1位置的字符去跟i-1位置的字符去比较，
				// 莫不如直接让cn=cn+1后，让i-1位置的字符去与cn位置的字符比较，所以cn要++，cn=cn+1
				// 三步并做一步
				next[i++] = ++cn;
			} else if (cn > 0) {
				// match[i - 1] != match[cn] 并且 cn还能往左跳，让cn往左跳
				cn = next[cn];
			} else {
				// match[i - 1] != match[cn] 并且 cn到了0位置了，
				// 不能再往左跳，那么next[i]==0,让i+1后继续循环求解
				next[i++] = 0;
			}
		}
		return next;
	}

	// for test
	public static String getRandomString(int possibilities, int size) {
		char[] ans = new char[(int) (Math.random() * size) + 1];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
		}
		return String.valueOf(ans);
	}

	public static void main(String[] args) {
		int possibilities = 5;
		int strSize = 20;
		int matchSize = 5;
		int testTimes = 5000000;
		System.out.println("test begin");
		for (int i = 0; i < testTimes; i++) {
			String str = getRandomString(possibilities, strSize);
			String match = getRandomString(possibilities, matchSize);
			// 使用系统函数作为对数器
			if (getIndexOf(str, match) != str.indexOf(match)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish");
	}

}
